package com.shixianjun;

import com.shixianjun.tools.Tools;

/**
 * 给定两个等长的数组
 * 数组1 ： 存储物品的重量 weights 正整数
 * 数组2 ： 存储数组的价值 prices 正整数
 *
 * 物品0 的重量存储在weights[0]中   物品0 的价值存储在prices[0]中
 * 物品1 的重量存储在weights[1]中   物品0 的价值存储在prices[1]中  以此类推
 *
 * 给定一个背包 限制背包的最大容量
 * 给出 背包装最大价值方案的 价格
 * */
public class 背包问题 {
    public static void main(String[] args) {
        int length = 60;
        int bagLimit = 30;
        int[] weights = Tools.randomIntArray(length, 20);
        int[] prices = Tools.randomIntArray(length, 10);

//        int[] weights = {3, 2, 4, 7, 3, 3, 1, 7};
//        int[] prices = {5, 6, 3, 19, 12, 4, 2, 3};

        Tools.printIntArray("weights", weights);
        Tools.printIntArray("prices ", prices);
        System.out.print("maxPrice1 :" + maxPrice1(weights, prices, bagLimit) + "\n");
        System.out.print("maxPrice2 :" + maxPrice2(weights, prices, bagLimit) + "\n");
    }

    public static int maxPrice1(int[] weights, int[] prices, int bagLimit) {

//        Function blockCode = () -> {};
//        Tools.printElapsedTime("maxPrice1", increase);

        long start = System.currentTimeMillis();
        int result = process1(weights, prices, 0, bagLimit);
        long end = System.currentTimeMillis();
        System.out.print("maxPrice1耗时: " + (end - start) + "毫秒\n");
        return result;
    }

    public static int process1(int[] weights, int[] prices, int index, int bagLimit) {
        if (bagLimit < 0) {
            return -1;
        }
        if (index >= weights.length) {
            return 0;
        }

        // 不拿当前物品
        int p1 = process1(weights, prices, index + 1, bagLimit);

        // 拿当前物品
        int p2 = 0;
        int next = process1(weights, prices, index + 1, bagLimit - weights[index]);
        if (next != -1) {
            p2 = prices[index] + next;
        }

        return Math.max(p1, p2);
    }

    public static int maxPrice2(int[] weights, int[] prices, int bagLimit) {
        int[][] dp = new int[weights.length + 1][bagLimit + 1];

        for (int i = 0; i <= weights.length; i++) {
            for (int j = 0; j <= bagLimit; j++) {
                dp[i][j] = -2;
            }
        }

        long start = System.currentTimeMillis();
        int result = process2(weights, prices, 0, bagLimit, dp);
        long end = System.currentTimeMillis();
        System.out.print("maxPrice2耗时: " + (end - start) + "毫秒\n");
        return result;
    }

    public static int process2(int[] weights, int[] prices, int index, int bagLimit, int[][] dp) {

        if (bagLimit < 0) {
            return -1;
        }

        if (dp[index][bagLimit] != -2) {
            return dp[index][bagLimit];
        }

        int ans = 0;
        if (index >= weights.length) {
            ans = 0;
        } else {
            int p1 = process2(weights, prices, index + 1, bagLimit, dp);

            int p2 = 0;
            int next = process2(weights, prices, index + 1, bagLimit - weights[index], dp);
            if (next != -1) {
                p2 = prices[index] + next;
            }
            ans = Math.max(p1, p2);
        }
        dp[index][bagLimit] = ans;
        return ans;
    }
}
